#include <stdio.h>

int called;
int muls;

long double poww(int base, int exp)
{
    /* pow := (base ^ exp/2) * (base ^ exp/2) If exp even
              base * (base ^ exp/2) * (base ^ exp/2) If exp odd
    */
    long double pow_by_2;
    long double rval;

    called ++;

    if (exp == 1)
    {
        return base;
    }

    if (exp == 0)
    {
        return 1;
    }
    
    pow_by_2 = poww(base, exp/2);
    rval = pow_by_2 * pow_by_2;
    printf("%d * %d\n", exp/2, exp/2);
    muls++;

    if (exp & 1)
    {
        rval *= base;
        muls++;
        printf("%d * %d\n", exp - 1, 1);
    }

    return rval;
}

int main(void)
{
    int base, exp;
    printf("Enter base: ");
    scanf("%d", &base);

    printf("Enter exponent: ");
    scanf("%d", &exp);

    printf("%d^%d: %Lf\n", base, exp, poww(base, exp));
    printf("Called %d times. Multiplies: %d\n", called, muls);

    return 0;
}
